package Z.dailyExercise._0225;

import java.util.HashMap;
import java.util.Map;

public class _剑指Offer10I斐波那契数列 {
    public static void main(String[] args) {
        _剑指Offer10I斐波那契数列 test = new _剑指Offer10I斐波那契数列();
        System.out.println(test.fib(5));
    }

    /**
     * 超时了！！因为重复计算了 同时还有数字过大溢出的情况
     * @param n
     * @return
     */
    public int fib(int n) {
        if (n<2){
            return n;
        }
        return fib(n-1)+fib(n-2);

    }

    /**
     * 防止溢出的版本
     *
     */
    int constant = 1000000007;
    public int fib1(int n) {
        if (n<2){
            return n;
        }
        int a = fib(n-1)%constant;
        int b = fib(n-2)%constant;
        return (a+b)%constant;
    }

    /**
     * 减少重复计算版本 将计算结果存在hashmap中
     */
    //int constant = 1000000007;
    Map<Integer,Integer> map = new HashMap<>();
    public int fib2(int n) {
        if (n<2){
            return n;
        }

        if (map.containsKey(n)){
            return map.get(n);
        }
        int a = fib(n-1)%constant;
        map.put(n-1,a);
        int b = fib(n-2)%constant;
        map.put(n-2,b);
        int res =(a+b)%constant;
        map.put(n,res);

        return res;

    }


}
